package tsb.trinhnx.main;

import java.util.Arrays;

public class main {
	private static int count = 0;

	private long multiple(long a, long b) {
		++count;
		if (b == 0)
			return 0;
		if (b == 1)
			return a;
		return a + multiple(a, b - 1);
	}

	// Assume same length
	private void test(char[] x, char[] y) {
		int x_length = x.length;
		int y_length = y.length;

		if (x_length == 1 && y_length == 1) {
			int x1 = x[0] - '0';
			int x2 = y[0] - '0';
			System.out.println("Final: " + x1 * x2);
			return;
		}
		// divide and conquer
		int x_half = x_length / 2;
		int y_half = y_length / 2;
		System.out.println("x half" + x_half + "\ty_half" + y_half);
		// Separate the x , y array into 2 sub array
		char[] x_left = Arrays.copyOfRange(x, 0, x_half);
		char[] x_right = Arrays.copyOfRange(x, x_half, x_length);
		char[] y_left = Arrays.copyOfRange(y, 0, y_half);
		char[] y_right = Arrays.copyOfRange(y, y_half, y_length);

		test(x_left, y_left);
		test(x_right, y_right);
		test(sum(x_right, y_right), sum(x_left, y_left));
	}

	// sum of 2 array negative int
	// also assum same length
	private char[] sum(char[] x, char[] y) {
		int carry = 0;
		StringBuilder sb = new StringBuilder();
		for (int i = x.length - 1; i >= 0; i--) {
			int x1 = x[i] - '0';
			int y1 = y[i] - '0';

			int value = (x1 + y1 + carry) % 10;
			carry = (x1 + y1 + carry) / 10;
			sb.append(value);
		}
		if (carry > 0)
			sb.append(carry);
		String temp = sb.reverse().toString();
		char[] result = new char[temp.length()];
		for (int i = 0; i < temp.length(); i++) {
			result[i] = temp.charAt(i);
		}
		return result;
	}

	public static void main(String[] args) {
		// Calculate 2^1000 = 1024^100
		long start = System.currentTimeMillis();
		BigNumber result = BigNumber.ONE;
		for (int j = 0; j < 100; j++) {
			BigNumber temp = new BigNumber(1024);
			result = result.multipleBigNumber(temp);
		}
		final String out = result.toString();
		int sum = 0;
		for (int i = 0; i < out.length(); i++) {
			sum = sum + (out.charAt(i) - '0');
		}
		System.out.println("Sum: " + sum + "\n" + out);
		System.out.println("Time: " + (System.currentTimeMillis() - start));
	}

	// Example for 4 characters
	private int testKaratsuba(int x, int y, int length) {
		if (length == 1) {
			return x * y;
		}
		int temp_length = length;
		int x1 = x / (int) Math.pow(10, length / 2);
		int x2 = x % (int) Math.pow(10, length / 2);
		int y1 = y / (int) Math.pow(10, length / 2);
		int y2 = y % (int) Math.pow(10, length / 2);
		System.out.println("x: " + x + "\tx1: " + x1 + "\tx2:" + x2);
		System.out.println("y: " + y + "\ty1: " + y1 + "\ty2:" + y2);
		int U = testKaratsuba(x1, y1, temp_length / 2);
		int V = testKaratsuba(x2, y2, temp_length / 2);
		int W = testKaratsuba(x1 - x2, y1 - y2, temp_length / 2);
		int Z = U + V - W;
		System.out.println("Length:" + length + "\tTemp " + temp_length);
		System.out.println("U: " + U + "\tV: " + V + "\tW: " + W + "\tZ: " + Z);
		int T = U * (int) Math.pow(10, length) + Z * (int) Math.pow(10, length / 2) + V;
		System.out.println();
		return T;
	}
}
